# 广度优先搜索
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        # 广度优先搜索
        if not root:
            return False

        resList = []
        que = collections.deque([root])
        queVal = collections.deque([root.val])
        while que:
            node = que.popleft()
            temp = queVal.popleft()
            if not node.left and not node.right:
                if temp == sum:
                    return True
            if node.left:
                que.append(node.left)
                queVal.append(node.left.val + temp)
            if node.right:
                que.append(node.right)
                queVal.append(node.right.val + temp)
        return False

# 深度优先搜索：递归】
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == sum
    return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
